package ncse.checkerOP;

import ncse.bpNeuralNetworks.BpNeuralNetworks;

/**
 *	Alpha beta 剪枝 和 MaxMin 假设前提：
 *  1. 双方都按照自己认为的最佳着法行棋
 *  2. 对给定的盘面有一个分值评估，这个评估值永远是从一方（搜索程序）来评价的。
 *  	红方有利，则给一个整数；
 *  	黑方有利，则给一个负数 。
 *  （如果红方有利时返回整数，当轮到黑方走棋时，评估值又转换到黑方的观点，如果认为黑方有利，也返回整数，这种评估方法都不适合于常规的算法描述）
 *  3. 当我们的搜索程序看来（Max），分值大的数表示更加对自己有利，而对于对方来说，他会选择分值最小的着法（分值小表述更加对min有利）。
 */
public class Checker {
	private static final int N = 4;
	private static final int SIZE = N * N;
	private static final int MAXVAL =  Short.MAX_VALUE;
	private static final int MINVAL =  Short.MIN_VALUE;
	private static final int computer = -1;
	private static final int player = 1;
	private int whofirst = 0;
	
	public void setWhofirst(int whofirst) {
		this.whofirst = whofirst;
	}

	private int m_chess_board[];
	private BpNeuralNetworks bpnet;

	public Checker() {
		// TODO Auto-generated constructor stub
		this.m_chess_board = new int[SIZE];
		bpnet = new BpNeuralNetworks();
		bpnet.read_weight();
		this.clear_board();
	}
	
	public void clear_board() {
		for (int i = 0; i < SIZE; i++) {
			this.m_chess_board[i] = 0;
		}
	}

	public int get_chess_board_val(int i, int j) {
		return this.m_chess_board[i * N + j];
	}

	// 打印棋盘函数。
	// 输入:void
	// 返回值：void
	@SuppressWarnings("unused")
	private void print_chess_board(int[] chess_board) {
		int i = 0, j = 0;
		for (i = 0; i < N; i++) {
			for (j = 0; j < N; j++) {
				if (j < N - 1) {
					System.out.println(chess_board[i * N + j] + "  ");
				} else {
					System.out.println(chess_board[i * N + j] + "  \n");
				}
			}
		}
		return;
	}

	// 在棋盘(x,y)处放置棋子。棋子类型为枚举piece∈{A,B}。
	// 输入：棋盘、x、y、棋子类型。
	// 返回值：void
	private void place_piece_on_chess_board(int[] chess_board, int pos, int type) {
		int x = pos/N;
		int y = pos%N;
		if (pos < 16 && pos >= 0)
			chess_board[x * N + y] = type;
		else {
			System.out.println("x = " + x + "  y = " + y);
		}
	}

	public void place_piece(int pos, int type) {
		place_piece_on_chess_board(this.m_chess_board, pos, type);
	}

	// 测试指定起点与步长的N个数数否相等，相等返回数值
	// 否则返回0
	private int test_N_num_equal(int[] chess_board, int start, int step) {
		int i = 0;
		int check_flag = 1;
		for (i = 0; i < N - 1; i++) {
			if (chess_board[start + i * step] != chess_board[start + (i + 1)
					* step]) {
				check_flag = 0;
				break;
			}
		}
		if (check_flag == 1 && chess_board[start + i * step] != 0) {
			return chess_board[start + i * step];
		}
		return 0;
	}

	// 测试当前棋局谁赢。
	// 输入：棋盘。
	// 返回值：为0表示A、B都没赢，为1表示A胜，为-1表示B胜。
	private int test_who_win(int[] chess_board) {
		// 分别测试一行、一列、两个对角线连成一线四种情况下的输赢

		int ret = 0;
		for (int i = 0; i < N; i++) {
			// 行
			ret = test_N_num_equal(chess_board, (i * N), 1);
			if (ret != 0)
				return ret;
			// 列
			ret = test_N_num_equal(chess_board, i, N);
			if (ret != 0)
				return ret;
		}
		ret = test_N_num_equal(chess_board, 0, (N + 1));
		if (ret != 0)
			return ret;
		ret = test_N_num_equal(chess_board, (N - 1), (N - 1));
		if (ret != 0)
			return ret;
		return 0;
	}

	public int who_win() {
		return test_who_win(this.m_chess_board);
	}

	// 测试当前棋盘（博弈树结点）属于极大结点或极小结点。
	// 输入：棋盘。
	// 返回值：为1表示当前为极大结点，为-1表示当前为极小结点。
	private int test_node_type(int[] chess_board) {
		// 可以用当前双方棋子数量来判断极大/极小结点
		int count_of_computer = 0, count_of_player = 0;
		int i = 0;
		for (i = 0; i < SIZE; i++) {
			if (chess_board[i] == computer) {
				count_of_computer++;
			} else if (chess_board[i] == player) {
				count_of_player++;
			}
		}
		if (count_of_computer == count_of_player){
			return whofirst;
		}else if (count_of_computer > count_of_player) {
			return player;
		} else {
			return computer;
		}
	}

	// 测试棋盘是否下满。
	// 输入：棋盘。
	// 返回值：下满返回true，否则返回false。
	private boolean test_if_chess_board_full(int[] chess_board) {
		int i = 0;
		for (i = 0; i < SIZE; i++) {
			if (chess_board[i] == 0) {
				return false;
			}
		}
		return true;
	}

	public boolean is_chess_board_full() {
		return test_if_chess_board_full(this.m_chess_board);
	}

	// 评估函数。
	// 输入：当前棋局。
	// 返回值：棋局对应评估函数值。
	private int evaluation_function(int[] chess_board) {
		if (test_who_win(chess_board) == 1) {
			return MAXVAL;
		} else if (test_who_win(chess_board) == -1) {
			return MINVAL;
		} else if (test_if_chess_board_full(chess_board)) {
			return 0;
		}else {
			int temp = (int)(bpnet.BP_net_value(chess_board)  * MAXVAL);
			return temp;
		}
	}
	
	/**
	 * α-β剪枝算法：
	 * 在搜索过程中，根据α、β的值进行决策，
	 * 如果某【着法】的结果大于或等于beta，那么这是很差的【着法】，因此可以废弃，剪枝操作（找最小的beta）
	 */
	
	// 搜索当前结点倒推值。
	// 输入：当前棋局、默认深度（默认为0）、最大深度、祖先数组、当前结点类型。
	// 返回值：棋局倒推值。
//	private int get_backed_up_value_of_node(int[] chess_board, int h, int[] ancestor, int root_type) {
//		int i = 0, j = 0;
//		if (h > 0) {
//			// 如果是叶子结点，返回评估值（神经网络在评估值中）
//			return evaluation_function(chess_board);
//		} else {
//			int backed_up_value;
//			int node_type = 0;
//			int usr_no = 0;
//			int node_value = -1;
//			int max_node_value = MINVAL, min_node_value = MAXVAL;
//			for (i = 0; i < SIZE; i++) {
//				if (chess_board[i] == 0) {
//					
//					place_piece_on_chess_board(chess_board, i, test_node_type(chess_board));
//					backed_up_value = get_backed_up_value_of_node(chess_board, (--h), ancestor, root_type);
//					place_piece_on_chess_board(chess_board, i, 0);
//					node_type = test_node_type(chess_board);
//					usr_no = (node_type + 1) == 2 ? node_type : 0;
//
//					if (node_type == computer) {
//						if (backed_up_value > max_node_value) {
//							max_node_value = backed_up_value;
//						}
//						node_value = max_node_value;
//					} else {
//						if (backed_up_value < min_node_value) {
//							min_node_value = backed_up_value;	
//						}
//						node_value = min_node_value;
//					}
//
//					// 根据各祖先结点的α或β值来剪枝
//					// 此处，由于node_type可为-1、1两种情况，
//					// 故将极大极小乘node_type后，可以合并看待
//					boolean continue_search = true;
//					for (j = 0; j < h; j++) {
//						if ((node_type * node_value) > (node_type * ancestor[j])) {
//							continue_search = false;
//							break;
//						}
//					}
//					if (continue_search == false) {
//						break;
//					}
//				}
//			}
//			// 完成叶子结点的搜索后，更新各祖先的α-β值
//			if (h <= 0) {
//				int flag = (node_type == root_type) ? 1 : -1;
//				if ((h - 1) % 2 != usr_no) {
//					if ((flag * node_value) > (flag * ancestor[h - 1])) {
//						ancestor[h - 1] = node_value;
//					}
//				} else {
//					if ((flag * node_value) < (flag * ancestor[h - 1])) {
//						ancestor[h - 1] = node_value;
//					}
//				}
//
//			}
//			return node_value;
//		}
//	}

		// 搜索当前结点倒推值。
		// 输入：当前棋局、默认深度（默认为0）、最大深度、祖先数组、当前结点类型。
		// 返回值：棋局倒推值。
		private int get_backed_up_value_of_node(int[] chess_board, int h, int alpha, int beta) {
			int i = 0;
			if (h == 0) {
				// 如果是叶子结点，返回评估值（神经网络在评估值中）
				return evaluation_function(chess_board);
			} else {
				int backed_up_value = -1;
				
				for (i = 0; i < SIZE; i++) {
					if (chess_board[i] == 0) {
						
						place_piece_on_chess_board(chess_board, i, test_node_type(chess_board));
						backed_up_value = -get_backed_up_value_of_node(chess_board, h-1, -beta, -alpha);
						place_piece_on_chess_board(chess_board, i, 0);

						// 根据各祖先结点的α或β值来剪枝
						// 此处，由于node_type可为-1、1两种情况，
						// 故将极大极小乘node_type后，可以合并看待
						
						if (backed_up_value >= beta) {
							return alpha;
						}
						
						if (backed_up_value > alpha) {
							alpha = backed_up_value;
						}
					}
					
				}
				return alpha;
			}
		}
	
	public int get_next_step() {
		int i = 0;
		int max = MINVAL - 1;
		int step = -1;
		int back_up_val;
//		int ancestor[] = new int[SIZE];
		int alpha = -1, beta = 1;
		for (i = 0; i < SIZE; i++) {
			if (this.m_chess_board[i] != 0) {
				continue;
			}
//			init_ancestor(ancestor, test_node_type(this.m_chess_board));
			place_piece_on_chess_board(this.m_chess_board, i, computer);
			//back_up_val = get_backed_up_value_of_node(this.m_chess_board, 8, ancestor, test_node_type(this.m_chess_board));
			back_up_val = get_backed_up_value_of_node(this.m_chess_board, 8, alpha, beta);
			place_piece_on_chess_board(this.m_chess_board, i, 0);
	//		System.out.println("back_up_val is " + back_up_val + " at "
	//				+ (i / N) + ", " + (i % N) + " \n");
			if (back_up_val > max) {
				max = back_up_val;
				step = i;
			}
		}
		return step;
	}
	
	public void train_mode() {
	    // 以下是用机器学习/调整神经网络的代码进行模型训练
		// 通过随机生成棋局并计算其倒退值，让神经网络调整权重，
	    // 即对战双方都是电脑
	    int computer1 = -1;
	    int computer2 = 1;
		try {
			int learn_times = 10;
			int temp_learn_times = 0;
			bpnet.init_weight();
			while(true) {
				int count = 0;
				this.clear_board();
				this.whofirst = computer1;
				while(!this.test_if_chess_board_full(this.m_chess_board) &&
						this.test_who_win(this.m_chess_board) == 0) {
					while(count < SIZE) {
						int r = (int)(Math.random() * 100);
						int temp = r % (SIZE);
						if (this.m_chess_board[temp] == 0) {
							if (count % 2 == 0) {
								this.place_piece_on_chess_board(this.m_chess_board, temp, computer1);								
							} else {
								this.place_piece_on_chess_board(this.m_chess_board, temp, computer2);
							}
							break;
						}
					}
					count ++;
					if (count >= 8) {
						int alpha = MINVAL, beta = MAXVAL;
						int backed_up_value = get_backed_up_value_of_node(this.m_chess_board, 8, alpha, beta);
						bpnet.adjust_BP_net_weight(this.m_chess_board, backed_up_value);
						temp_learn_times ++;
						System.out.println("learn " + temp_learn_times + " times.\n");
					}
				}
				if (learn_times-- > 0) {
					break;
				}
			}
			bpnet.write_mode();
		} catch (Exception e) {
			
		}
	}
}
